Non-binary values appear in many forms across a processor. Non-binary values may be multibit values, for example, up to 32 bits in length, though non-binary values may not be limited to this length. Non-binary values may include data values, data memory addresses and indirect branch targets. Accurately predicting these values may give a substantial performance gain. For example, an instruction that reads a value stored in a register may be dependent on the last instruction that wrote the value into the register. A predicted value enables the processor to break a data dependency chain between the two instructions and increase the instruction level parallelism. As a second example, load instructions fetch data from an addressed memory location into a register. The memory address may be given as a function of immediate values and register values. Before the memory can be read, the memory address should be calculated. If the address could be predicted, it not only would save the time required for its calculation, but it may save the time waiting for any register value required for the address calculation. As another example, an indirect branch may take a different target each time that it is executed. An accurate target prediction has a significant performance potential, as a misprediction leads to a pipeline flush. Moreover, it is expected in future software applications that the relative amount of indirect branches will be higher, which may result in increased performance for these applications.
Processor predictors also may perform data value prediction. Data value prediction uses prediction schemes such as last value prediction, stride prediction and pattern-based prediction. Memory address prediction uses prediction schemes that include last value prediction and stride prediction. Some of these schemes are discussed below.
Non-binary values may exhibit various common behaviors. First, values may follow a general repeating pattern, or shift. For example, a,b,b,c,a,b,b,c,a,b,b,c may be a shift pattern. Second, values may follow a general repeating pattern that contains a long repeating value sequence, or count. For example, a,a,a,a,a,b,c,a,a,a,a,a,b,c may be a count pattern. Third, values may follow a general, but not necessarily repeating, pattern that contains a constant stride sequence, or stride. For example, 2,4,6,8,5,1,2,4,6,8,5,1 may be a stride pattern. Though both stride and count patterns are special cases of the shift pattern, these cases may be predicted in a more efficient manner using special predictor modes. Prediction modes may save predictor space and may provide a better prediction rate for a given predictor space. One such predictor may be a hybrid predictor that predicts each pattern using a different component, and a chooser is used for selecting the component that makes the prediction. The chooser, however, adds another logic components to the predictor for each mode, and impedes transition between prediction modes, thus reducing accuracy for a given predictor space. Thus, a need has arisen for a non-binary predictor with increased efficiency without additional logic components.